/*!	 curveset.cpp
**	 Curve Set Implementation File
**
**	Copyright (c) 2002-2005 Robert B. Quattlebaum Jr., Adrian Bentley
**
**	This package is free software; you can redistribute it and/or
**	modify it under the terms of the GNU General Public License as
**	published by the Free Software Foundation; either version 2 of
**	the License, or (at your option) any later version.
**
**	This package is distributed in the hope that it will be useful,
**	but WITHOUT ANY WARRANTY; without even the implied warranty of
**	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
**	General Public License for more details.
**
*/

#ifdef USING_PCH
#	include "pch.h"
#else
#ifdef HAVE_CONFIG_H
#	include <config.h>
#endif

#include "curve_helper.h"
#include "curveset.h"
#include "blinepoint.h"
#include <ETL/bezier>
#include <vector>
#include <list>
#include <set>

#endif

using namespace std;
using namespace etl;
using namespace synfig;

const Real ERROR = 1e-10;

template < typename T >
inline bool Zero(const T &a, const T &tol = (T)ERROR)
{
    return a < tol && a > -tol;
}

CurvePoint::CurvePoint(const Point &pin, const Vector &left, const Vector &right)
    : p(pin), l(left), r(right)
{
}

CurvePoint::CurvePoint(const BLinePoint &bpoint)
{
    p = bpoint.get_vertex();

    l = p + bpoint.get_tangent1() * (1 / 3.0f);
    r = p + bpoint.get_tangent2() * (1 / 3.0f);
}

struct ipoint {
    int 	curveindex;
    int		vertindex;
    float	tvalue;

    ipoint	*next;
    ipoint	*prev;
    ipoint	*neighbor;

    int 	go_in;	// going in = 1, coming out = -1

    ipoint():
        curveindex(),
        vertindex(),
        tvalue(),
        go_in()
    {
        next = this;
        prev = this;
        neighbor = NULL;
    }

    bool operator<(const ipoint &rhs) const
    {
        if (curveindex == rhs.curveindex) {
            if (vertindex == rhs.vertindex) {
                return tvalue < rhs.tvalue;
            } else {
                return vertindex < rhs.vertindex;
            }
        } else {
            return curveindex < rhs.curveindex;
        }
    }

    bool operator>(const ipoint &rhs) const
    {
        return rhs < *this;
    }

    void insert_after(ipoint *i)
    {
        // from: next - next.prev

        ipoint 	*bef = this,
                 *aft = next;

        // assuming the input point is not connected to anything, we don't have to do anything with it...
        bef->next = i;
        i->prev = bef;
        aft->prev = i;
        i->next = aft;
    }

    void insert_before(ipoint *i)
    {
        // from: prev.next - prev

        ipoint 	*bef = prev,
                 *aft = this;

        // assuming the input point is not connected to anything, we don't have to do anything with it...
        bef->next = i;
        i->prev = bef;
        aft->prev = i;
        i->next = aft;
    }

    void insert_sorted(ipoint *i)
    {
        ipoint *search = this;

        if (*i < *this) {
            // we go forward
            search = this;

            do {
                search = search->next;
            } while (*i < *search && search != this); // ending conditions...

            // now we insert previously...
            search->insert_before(i);
        } else if (*i > *this) {
            // we go backwards...
            search = this;

            do {
                search = search->prev;
            } while (*i > *search && search != this); // ending conditions...

            // now we insert previously...
            search->insert_after(i);
        }
    }
};

enum SetOp {
    INTERSECT	= 0,
    UNION,
    SUBTRACT,
    INVSUBTRACT,
    NUM_SETOPERATIONS
};

class PolygonClipper
{
public:
    typedef vector<ipoint *>	CurveInts; // in no particular order

    vector<CurveInts>	c1ints;
    vector<CurveInts>	c2ints;

    // get the intersections
    void GetIntersections(const CurveSet &lhs, const CurveSet &rhs)
    {
        CIntersect	isect;
        bezier<Point>	b1, b2;

        int i1, j1, ci1, s1;
        int i2, j2, ci2, s2;

        // clear out so everyone's happy
        c1ints.clear();
        c2ints.clear();

        c1ints.resize(lhs.set.size());
        c2ints.resize(rhs.set.size());

        // loop through everyone and be happy...

        // intersect each curve with each other curve, and we're good
        for (ci1 = 0; ci1 < (int)lhs.set.size(); ++ci1) {
            const CurveSet::region &cur1 = lhs.set[ci1];
            s1 = cur1.size();

            for (j1 = s1 - 1, i1 = 0; i1 < s1; j1 = i1++) {
                b1[0] = cur1[j1].p;
                b1[3] = cur1[i1].p;
                b1[1] = b1[0] + cur1[j1].r / 3;
                b1[2] = b1[3] - cur1[i1].l / 3;

                for (ci2 = 0; ci2 < (int)rhs.set.size(); ++ci2) {
                    const CurveSet::region &cur2 = rhs.set[ci2];
                    s2 = cur2.size();

                    for (j2 = s2 - 1, i2 = 0; i2 < s2; j2 = i2++) {
                        b2[0] = cur2[j2].p;
                        b2[3] = cur2[i2].p;
                        b2[1] = b2[0] + cur2[j2].r / 3;
                        b2[2] = b2[3] - cur2[i2].l / 3;

                        isect(b1, b2);

                        for (int index = 0; index < (int)isect.times.size(); ++index) {
                            // prepare basic intersection information
                            ipoint *ip1 = new ipoint, *ip2 = new ipoint;

                            // set parameters
                            ip1->curveindex = ci1;
                            ip1->vertindex = j1;
                            ip1->tvalue = isect.times[index].first;
                            ip2->curveindex = ci2;
                            ip2->vertindex = j2;
                            ip2->tvalue = isect.times[index].second;

                            // set neighbors
                            ip1->neighbor = ip2;
                            ip2->neighbor = ip1;

                            // first one just goes on end of list
                            c1ints[ci1].back()->insert_sorted(ip1);
                            c1ints[ci1].push_back(ip1);

                            // second one must go in order
                            c2ints[ci2].back()->insert_sorted(ip2);
                            c2ints[ci2].push_back(ip2);

                            // we're all good...
                        }
                    }
                }
            }
        }

        // Now figure out the containment properties of each int point
        Point p;
        int inside = 0;

        for (int i = 0; i < (int)c1ints.size(); ++i) {
            if (c1ints[i].size() == 0) {
                continue;
            }

            // must test insideness for the edges
            ipoint *start, *iter;
            start = iter = c1ints[i].front();

            // i == iter->curveindex == the index of the current curve we're looking at

            // set the initial insideness on the other curve...
            p = lhs.set[i][iter->vertindex].p;
            inside = rhs.intersect(p) % 2; // if it's inside by the even odd rule

            do {
                iter->go_in = inside ? -1 : 1; // leaving if inside, or coming in if not
                inside = !inside;
                iter = iter->next;
            } while (iter != start); // I hope this isn't an infinite loop!
        }

        // and curve 2
        for (int i = 0; i < (int)c2ints.size(); ++i) {
            if (c2ints[i].size() == 0) {
                continue;
            }

            // must test insideness for the edges
            ipoint *start, *iter;
            start = iter = c1ints[i].front();

            // set the initial insideness on the other curve...
            p = rhs.set[i][iter->vertindex].p;
            inside = lhs.intersect(p) % 2; // if it's inside by the even odd rule

            do {
                iter->go_in = inside ? -1 : 1; // leaving if inside, or coming in if not
                inside = !inside;
                iter = iter->next;
            } while (iter != start); // I hope this isn't an infinite loop!
        }
    }

    bool ConstructSet(CurveSet &/*c*/, const CurveSet &lhs, const CurveSet &rhs, int type)
    {
        bool in1, in2;

        switch (type) {
        case INTERSECT: 			{
            in1 = true;
            in2 = true;
            break;
        }

        case UNION: 			{
            in1 = false;
            in2 = false;
            break;
        }

        case SUBTRACT: 			{
            in1 = true;
            in2 = false;
            break;
        }

        case INVSUBTRACT: 			{
            in1 = false;
            in2 = true;
            break;
        }

        default: {
            return false;
        }
        }

        // traverse path based on inside flags

        // fill all the paths of native stuff
        set<ipoint *>	ipset;

        for (int ci = 0; ci < (int)c1ints.size(); ++ci) {
            for (int i = 0; i < (int)c1ints[ci].size(); ++i) {
                ipset.insert(c1ints[ci][i]);
            }
        }

        //
        while (ipset.size() > 0) {
            // start from one point (always on curveset 1) and traverse until we find it again
            ipoint *start, *iter;
            start = iter = *ipset.begin();

            // All the info to swap when we transition curves...
            const CurveSet *cur, *other;
            bool curin, otherin;
            bool delcur = true;

            set<ipoint *>::iterator deliter;

            // int ci,i1,i2,size;
            // float t1,t2;

            CurveSet::region	current;
            CurvePoint	cp;

            cur = &lhs;
            other = &rhs;
            curin = in1;
            otherin = in2;
            delcur = true;

            do {
                // remove the current iter from the set
                if (delcur) {
                    deliter = ipset.find(iter);

                    if (deliter != ipset.end()) {
                        ipset.erase(deliter);
                    }
                }

                // go to next and accumulate information
                iter = iter->next; // move to next and get its info



                // record all the stuff between us...
                // start on an intersection - get the curve point...

                // transition curves...
                iter = iter->neighbor;
                swap(cur, other);
                swap(curin, otherin);
                delcur = !delcur;
            } while (iter != start); // I hope THIS isn't an infinite loop
        }

        return true;
    }
};

void CurveSet::SetClamp(int &i, int &si)
{
    if (si > 0 && si < (int)set.size()) {
        if (i >= (int)set[si].size()) {
            i -= set[si].size();
            si++;
        } else if (i < 0) {
            i += set[si].size();
            si--;
        }
    }
}

void CurveSet::CleanUp(int /*curve*/)
{
}

/*	Detect intersections that are crazy happy good

	Performance annoyances:
	1) Recursing down to find an intersection at the end points that doesn't actually exist
		(can be helped a bit by not including the edges of bounding rectangles)
	2) Intersecting curves is slow... oh well

	Algorithm:
	1) Inside out scheme, track when edges go into and come out of various objects etc.

	+ doesn't require initial conditions
	- only works with odd-even rule
*/

CurveSet CurveSet::operator&(const CurveSet &/*rhs*/) const
{
    return *this;
}

CurveSet CurveSet::operator|(const CurveSet &/*rhs*/) const
{
    return *this;
}

CurveSet CurveSet::operator-(const CurveSet &/*rhs*/) const
{
    return *this;
}

int CurveSet::intersect(const Point &p) const
{
    int inter = 0, ci, i, j, s;
    bezier<Point>	b;

    for (ci = 0; ci < (int)set.size(); ++ci) {
        const vector<CurvePoint> &curve = set[ci];
        s = curve.size();

        for (j = s - 1, i = 0; i < s; j = i++) {
            b[0] = curve[j].p;
            b[3] = curve[i].p;
            b[1] = b[0] + curve[j].r / 3;
            b[2] = b[3] - curve[i].l / 3;

            inter += synfig::intersect(b, p);
        }
    }

    return inter;
}